package com.cqs.leetcode.hash;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

/**
 * Map + 数组
 *
 * @author lixqw
 * @date 2020/8/23
 */
public class RandomizedSet {

    /**
     * key: 元素
     * value: 元素在list中的索引
     */
    private HashMap<Integer, Integer> map = new HashMap<>();
    /**
     * 存储元素
     */
    private ArrayList<Integer> list = new ArrayList<>(1024);

    private Random rand = new Random();

    /**
     * Initialize your data structure here.
     */
    public RandomizedSet() {

    }

    public boolean insert(int val) {
        //1.判断元素是否存在
        boolean contains = map.containsKey(val);
        if (contains) {
            return false;
        }
        int size = list.size();
        map.put(val, size);
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        // 判断是否存在
        boolean contains = map.containsKey(val);
        if (!contains) {
            return false;
        }
        //核心思想: 将待删除的元素和数组最后一个元素位置交换（同是更新最后一个元素在map的中的信息）
        int idx = map.get(val);
        int swapKey = list.get(list.size() - 1);
        //数组最后一个元素的，更新[交换]到待删除元素的位置
        map.put(swapKey, idx);
        //更新元素
        list.set(idx, swapKey);
        //删除目标元素
        map.remove(val);
        //数组删除最后一个元素
        list.remove(list.size() - 1);
        return true;
    }

    /**
     * Get a random element from the set.
     */
    public int getRandom() {
        int size = list.size();
        if (size == 0) return -1;
        return list.get(rand.nextInt(size));
    }
}
